package bTree.LeetCode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class 组合总和3 {
    List<List<Integer>>res=new LinkedList<>();
    List<Integer>temp=new LinkedList<>();
    int sum=0;
    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k,n,1);
        return res;
    }

    public void backtracking(int k,int n,int index){
        if(temp.size()==k){
            if(sum==n){
                res.add(new LinkedList<>(temp));
            }
            return;
        }

        for (int i=index;i<=9;i++){
            temp.add(i);
            sum+=i;
            backtracking(k,n,i+1);
            temp.remove(temp.size()-1);
            sum-=i;
        }


    }
}